class Solution
{
public:
    bool check(int num)
    {
        int prev = INT_MAX;
        int cur = 0;
        while (num)
        {
            cur = num % 10;
            num /= 10;
            if (prev < cur)
                return false;
            prev = cur;
        }
        return true;
    }
    int monotoneIncreasingDigits(int n)
    {
        // 暴力做法
        for (int i = n; i >= 0; i--)
        {
            if (check(i))
                return i;
        }
        return -1;
    }
};

// 贪心做法 找到不满足递增的位置 接着改位置减少1 地位变为9999
class Solution
{
public:
    int monotoneIncreasingDigits(int n)
    {
        string num = to_string(n);
        int len = num.size();
        int pos = 0;
        while (pos + 1 < len && num[pos] <= num[pos + 1])
            pos++;
        if (pos + 1 >= len)
            return n;
        cout << pos << endl;
        char tem = num[pos];
        // 下面从pos位置往前找到第一个与他一样的位置
        for (int i = pos - 1; i >= 0; i--)
        {
            if (num[i] == tem)
            {
                pos = i;
            }
        }
        cout << pos << endl;
        for (int i = pos; i < len; i++)
        {
            if (i == pos)
            {
                num[i]--;
            }
            else
                num[i] = '9';
        }
        // reverse(num.begin(),num.end());
        // while(num.size()>1&&num[num.size()-1]=='0') num.pop_back();
        // reverse(num.begin(),num.end());
        cout << num;
        return stoi(num);
    }
};